import functools

class Solution(object):
    def minAbsDifference(self, nums, goal):
        n = len(nums)
        n1 = n // 2
        nums1 = nums[: n1]
        nums2 = nums[n1:]
        n2 = len(nums2)
        d1 = set()
        d2 = set()
        @functools.cache
        def dfs1(val):
            if val == 0:
                return 0
            else:
                last_val = val & (val - 1)
                wei = len(str(bin(val - last_val))) - 3
                return dfs1(last_val) + nums1[wei]

        @functools.cache
        def dfs2(val):
            if val == 0:
                return 0
            else:
                last_val = val & (val - 1)
                wei = len(str(bin(val - last_val))) - 3
                return dfs2(last_val) + nums2[wei]
        for val in range(1 << n1):
            d1.add(dfs1(val))
        for val in range(1 << n2):
            d2.add(dfs2(val))



        d1 = [goal - num for num in d1]
        d2 = list(d2)
        n1 = len(d1)
        n2 = len(d2)
        d1.sort()
        d2.sort()
        index1 = 0
        index2 = 0
        min_val = float('inf')
        while index1 < n1 and index2 < n2:
            if d1[index1] < d2[index2]:
                min_val = min(min_val, d2[index2] - d1[index1])
                index1 += 1
            else:
                if d1[index1] > d2[index2]:
                    min_val = min(min_val, d1[index1] - d2[index2])
                    index2 += 1
                else:
                    return 0
        return min_val


data = Solution()
nums = [5, -7, 3, 5]
goal = 6
print(data.minAbsDifference(nums, goal))
nums = [7,-9,15,-2]
goal = -5
print(data.minAbsDifference(nums, goal))